class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        int m = s1.size();
        int n = s2.size();
        if (m + n != s3.size())
            return false; // 长度都不匹配还判断什么
        s1 = ' ' + s1;
        s2 = ' ' + s2;
        s3 = ' ' + s3;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for (int i = 1; i <= m; ++i)
        {
            if (s1[i] == s3[i])
                dp[i][0] = true;
            else
                break;
        }
        for (int j = 1; j <= n; ++j)
        {
            if (s2[j] == s3[j])
                dp[0][j] = true;
            else
                break;
        }
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (s1[i] == s3[i + j] && dp[i - 1][j] == true)
                    dp[i][j] = true;
                else if (s2[j] == s3[i + j] && dp[i][j - 1] == true)
                    dp[i][j] = true;
            }
        }
        return dp[m][n];
    }
};

class Solution
{
public:
    int minimumDeleteSum(string s1, string s2)
    {
        // 求出两个字符串所有公共子序列，里面ascii值的最大和
        // 然后两个字符串ascii的和减两次ascii最大和，就得到删除的ascii最小和了
        // dp[i][j] : s1的0到i和s2的0到j，所有的子序列中，最大公共子序列的ascii的和
        int m = s1.size();
        int n = s2.size();
        s1 = ' ' + s1;
        s2 = ' ' + s2;
        int sum = 0;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                // 看最后一个位置情况讨论，有4种：
                // 1、有s[i]，有s[j]；2、有s[i]，没有s[j]；3、没有s[i]，有s[j]；4、没有s[i]，没有s[j]；
                if (s1[i] == s2[j])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + s1[i]); // 加上s2[j]也可以
                dp[i][j] = max(dp[i][j], max(dp[i - 1][j], dp[i][j - 1]));
                // 本来应该还有情况4的，但是因为求的是最大公共子序列的ascii的和，dp[i-1][j],dp[i][j-1]都包含了情况4
                // 所以不用考虑了
            }
        }
        for (auto e : s1)
            sum += e;
        for (auto e : s2)
            sum += e;
        sum = sum - ' ' * 2;              // 前面为了让s1和s2下标对应加了两个空格
        return sum - dp[m][n] - dp[m][n]; // 要减两次公共子序列最大ascii，因为s1有，s2也有！减完两次才剩下最小ascii删除和
    }
};

class Solution
{
public:
    int findLength(vector<int> &nums1, vector<int> &nums2)
    {
        // dp[i][j] : nums1必须以i结尾，nums2必须以j结尾
        // 因为子序列是可以不连续的，所以i+1，j+1,i+2....都是可以跟在我i-1，j-1，i-2等等任意位置的
        // 但是子数组就不行，子数组是要求连续的，我i+1必须跟在你i位置，你的i位置必须是前面结尾，我i+1才能接着
        int m = nums1.size();
        int n = nums2.size();
        int max_count = INT_MIN;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                // 都不相等了，就表示该位置结尾没有公共子数组
                //  else
                //      dp[i][j] = 0;
                max_count = max(max_count, dp[i][j]);
            }
        }
        return max_count;
    }
};



// 牛客网 01背包
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1001;
int n, V, v[N], w[N];
int dp[N][N];

int main() 
{
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) 
    {
        cin >> v[i] >> w[i];
    }
    // 问题1
    for(int i=1;i<=n;++i)// 物品编号
    {
        for(int j=1;j<=V;++j) // 背包容量
        {
            dp[i][j] = dp[i-1][j];// i位置物品不选，该情况一定存在
            if(j-v[i] >= 0)//判断一下取前面哪一个位置的值，使得背包容量足够我们这里选取i位置物品
                dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]); //加上i位置物品的价值
        }
    }
    cout << dp[n][V] << endl;
    // dp表清空内部数据
    memset(dp,0,sizeof(dp));
    // 问题2
    // -1表示i位置一个物品就直接大于背包最大容量了
    for(int j=1;j<=V;++j)
    {
        dp[0][j] = -1; // 物品为0没有，想使得背包容量为j这种情况是不存在的，-1
    }
    for(int i=1;i<=n;++i)// 物品编号
    {
        for(int j=1;j<=V;++j) // 背包容量
        {
            dp[i][j] = dp[i-1][j];// i位置物品不选，该情况一定存在
            if(j-v[i] >= 0 && dp[i-1][j-v[i]]!= -1) // 判断如果我选i位置物品，但是i位置物品的体积超过了背包容量，那么就不能选了
                dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]); //加上i位置物品的价值
        }
    }
    cout << (dp[n][V] == -1 ?0:dp[n][V]) << endl; //最后为-1表示所有物品的体积都大于背包容量，返回0
    return 0;
}


// 优化